package chapter01;

public class CountAndSay {
    /**
     * 递归求解
     * 思路：
     *      求n的字符 即求n-1的字符,再对n-1数字字符个数进行统计
     * 递归条件
     *      1.n==1 返回 "1"
     * 双指针两种思路
     *      1).初始start和end同时指向同一位置
     *          start=0 end=0
     *          无需最后分析最后一次得到的字符需不需要进行添加
     *      2).初始end指向start+1位置 (效率更高)
     *          start=0 end=start+1
     *          需要分析最后一次得到的字符需不需要进行添加
     *  打表 O(1)
     */
//    public String countAndSay(int n) {
//        if(n==1){
//            return "1";
//        }
//        String str=countAndSay(n-1);
//        StringBuilder builder=new StringBuilder();
//        int length=str.length();
//        int start=0;
//        int end=0;
//        while (end<length){
//            if(str.charAt(start)==str.charAt(end)){
//                while(end<length&&str.charAt(start)==str.charAt(end)){
//                    end++;
//                }
//            }
//            builder.append(end-start);
//            builder.append(str.charAt(start));
//            start=end;
//        }
//        return builder.toString();
//    }

    public String countAndSay(int n) {
        if(n==1){
            return "1";
        }
        String str=countAndSay(n-1);
        StringBuilder builder=new StringBuilder();
        int length=str.length();
        int start=0;
        int end=start+1;
        while (end<length){
            while(end<length&&str.charAt(start)==str.charAt(end)){
                end++;
            }
            builder.append(end-start);
            builder.append(str.charAt(start));
            start=end;
            end++;
        }
        if(start<length){
            builder.append(end-start);
            builder.append(str.charAt(start));
        }
        return builder.toString();
    }
}
